Network-wide data broadcast and data collection are fundamental operations in wireless networks. The goal of broadcasting is to transmit a message from a source to all the other nodes in the network. Several network protocols rely on broadcasting, for example, information dissemination, service/resource discovery, or routing in multihop wireless networks. Given that key applications of multihop wireless networks include disaster relief and rescue operations, military communication, and prompt object detection using sensors, the design of low-latency broadcasting scheme is essential to meeting stringent end-to-end delay requirements for higher-level applications. Typically, a data collection problem arises when data is gathered from wireless nodes to a fixed sink to process the data that can lead to related problems such as data aggregation or convergecast
Due to the property of wireless medium, interference is a fundamental limiting factor in wireless networks. When two or more nodes transmit a message to a common neighbor at the same time, collision occurs at the common node and the common node does not receive any of these messages. One of the earliest broadcast mechanisms employed is flooding, wherein every node in the network transmits a message to its neighbors after receiving it. Although flooding is extremely simple and easy to implement, flooding can be very costly and can lead to serious redundancy, bandwidth contention, and collision: a situation known as broadcast storm.
A few conventional systems present a mobility transparent broadcast scheme for mobile multi-hop radio networks, wherein, nodes compute their transmit times once in the beginning of transmission. Conventional systems also provide schemes with bounded latency, which have approximation factors that are linear and polylogarithmic in the number of network nodes. In effect, the schemes assume that the topology of the network is completely unknown. Although the schemes are attractive for highly mobile environments, their approximation factors are far from what is achievable in static and relatively less mobile environments.
Some other traditional systems prove that minimizing broadcast latency in wireless networks is NP-complete. The algorithm employed by these traditional systems, simultaneously achieves a constant approximation both for the latency as well as for the number of transmissions. However, the constant for the latency of their one-to-all algorithm is high. Further, a few systems provide centralized and distributed algorithms for broadcasting and experimentally study of their algorithms with respect to collision-free delivery, number of transmissions and broadcast latency. However, the distributed algorithm is not guaranteed to be collision-free and guarantees are not provided with respect to the number of transmissions and latency of the broadcast schedule.